package com.zsj.Tree;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author zsj
 * @Version 1.0
 * @Date 2024/4/13 15:08
 * @Description LCR 175. 计算二叉树的深度
 */
public class TreeMaxDeep {

    /**
     * 每次遍历到叶子节点的时候维护一次最大值
     * 叶子节点的定义是  左右子树都是null的节点
     */
    public int calculateDepth(TreeNode root) {
        int ans = 0;
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        TreeNode redo = null;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);//记录来时的路
                ans = Math.max(stack.size(), ans);//更新最大深度
                cur = cur.left;//沿着左边走
            } else {
                //说明左边走到头了
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == redo) {
                    //说明没有右子树 或者右子树已经被处理过了
                    redo = stack.pop();
                } else {
                    //说明右子树没有被处理
                    cur = peek.right;
                }
            }
        }
        return ans;
    }

    //递归思想 最大深度 就是去看左右子树两边的深度 那边更深 取哪边
    public int calculateDepth2(TreeNode root) {
        if (root == null) return 0;//节点为空
        //判断左右子树两边那边的节点深度要更深一些
        //每次调用递归都会+1
        return Math.max(calculateDepth2(root.left),
                calculateDepth2(root.right)) + 1;
    }

    //层序遍历思想
    public int calculateDepth3(TreeNode root) {
        /**
         * 层序遍历的思想
         * 就是每次循环 将所有的节点的子节点再加入队列中
         */
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                //左边不为空
                if (poll.left != null) queue.offer(poll.left);
                //右边不为空
                if (poll.right != null) queue.offer(poll.right);
            }
            //到这里说明得一层
            ans++;
        }
        return ans;
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1
                , new TreeNode(2, new TreeNode(4), null),
                new TreeNode(3, new TreeNode(5, new TreeNode(7), null), new TreeNode(6)));
        System.out.println(new TreeMaxDeep().calculateDepth3(treeNode));

    }
}
